package Stack;

import java.util.Stack;

/**
 *  题目 ：排序栈
 *  题目详情 ：
 *  栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。
 *  最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 *  该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 */
public class SortedStack {
    /**
     *  方法一 ：（不使用辅助栈）
     *  核心思想 ：递归
     *  （1）当栈为空/栈顶元素大于val（输入的值）时，可以直接将val元素压入栈中(即，代替当时栈顶元素的值)；
     *  （2）若是不满足以上条件，即使用临时变量temp来存储栈顶元素，同时将其弹栈；
     *  （3）弹栈后，再次将val值与弹栈后的栈顶元素进行比较（此处进行递归，递归的结束条件：（1）栈为空/（2）栈顶元素大于等于val（输入的元素））
     */
    /*
    Stack<Integer> stack;
    public SortedStack() {
        stack = new Stack<>();
    }

    public void push(int val) {
        sortStack(val);
    }

    private void sortStack(int val) {
        // 当stack中为空，或者 栈顶元素大于等于val（即输入的val为最小值时）
        if(stack.isEmpty() || stack.peek() >= val){
            stack.push(val);
            // 函数的返回值虽然是void，但是为了能够递归结束，需要进行返回return;
            return ;
        }
        int temp = stack.pop();
        // 此处使用递归，对于栈进行排序（递归结束条件，即找到栈中比val大的值/栈变为空栈时）
        sortStack(val);
        stack.push(temp);
    }

    // 弹栈
    public void pop() {
        if(stack.isEmpty()){
            return ;
        }
        stack.pop();
    }
    // 获取栈顶元素的值，并且将其返回
    public int peek() {
        if(stack.isEmpty()){
            return -1;
        }
        // 栈的peek操作，仅仅只是获取栈顶元素，并没有将栈顶元素弹出栈
        return stack.peek();
    }
    // 判断栈中是否为空
    public boolean isEmpty() {
        return stack.isEmpty();
    }
    */
    /**
     * 方法二 ：（使用辅助栈）
     * （1）只能使用一个临时栈存放数据
     * （2）入栈时，先将栈中小于val的数值暂存到临时栈中
     * （3）将val入栈
     * （4）再将临时栈中的数据push会栈中
     */
    Stack<Integer> stack;
    Stack<Integer> temp;
    // 定义临时栈，排序栈
    public SortedStack() {
        stack = new Stack<>();
        temp = new Stack<>();
    }

    public void push(int val) {
        // 当stack为空时，直接将val的值压入栈stack中
        if(stack.isEmpty()){
            stack.push(val);
            return;
        }
        // 当栈不为空 && val > 栈顶元素时，弹出stack的栈顶元素，同时将其加入到temp栈中去
        while(!stack.isEmpty() && val > stack.peek()){
            temp.push(stack.pop());
        }
        // 当（1) val <= 栈顶元素 （2）stack栈为空时，将val插入stack栈中
        stack.push(val);
        // 将temp栈中的所有元素，回溯到stack栈中
        while(!temp.isEmpty()){
            stack.push(temp.pop());
        }
        return;
    }

    public void pop() {
        if(stack.isEmpty()){
            return;
        }
        stack.pop();
    }

    public int peek() {
        if (stack.isEmpty()){
            return -1;
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}
